// 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

// 返回滑动窗口中的最大值。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/sliding-window-maximum
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
using namespace std;

// 看了题解，单调队列,递减

// 执行用时：
// 236 ms
// , 在所有 C++ 提交中击败了
// 75.56%
// 的用户
// 内存消耗：
// 128.9 MB
// , 在所有 C++ 提交中击败了
// 37.12%
// 的用户

class Solution {
public:
    class MYQueue{
        public:
            deque<int> que;
            void pop(int val){
                if(!que.empty()&&val==que.front()){
                    que.pop_front();
                }
            }

            void push(int val){
                while (!que.empty()&&val>que.back()){
                    que.pop_back();
                }
                que.push_back(val);                
            }

            int front(){
                return que.front();
            }
    };

    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len =nums.size();
        if(len<2){
            return nums;
        }
        vector<int> res;
        MYQueue que;
        for(int i=0;i<k;i++){
            que.push(nums[i]);
        }
        res.push_back(que.front());
        for(int i=k;i<nums.size();i++){
            que.pop(nums[i-k]);
            que.push(nums[i]);
            res.push_back(que.front());
        }
        return res;
    }
};